//
// Created by 高森森 on 2022/2/14.
//

#ifndef LEETCODE_SOLUTION43_H
#define LEETCODE_SOLUTION43_H
#include<iostream>
#include<vector>
#include<queue>
#include <math.h>
using namespace std;

class Solution43 {
public:
    //拓扑排序+贪心 用例无法过去，有反例
    int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
        if(relations.size()==0)
        {
            return ceil((double)n/k);
        }
        vector<int>indegree(n+1);
        vector<int>outdegree(n+1);
        vector<vector<int>>graph(n+1);
        for(auto edge:relations){
            graph[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
            outdegree[edge[0]]++;
        }
        int count=0;
        priority_queue<pair<int,int>>que;
        for(int i=1;i<=n;i++)
        {
            if(indegree[i]==0){
                que.emplace(outdegree[i],i);
            }
        }
        while(!que.empty()){
                int size=que.size();
                 size=size<k?size:k;
            for(int i=0;i<size;i++){
                auto node=que.top();
                que.pop();
                for(auto neigh:graph[node.second]){
                    indegree[neigh]--;
                    if(indegree[neigh]==0)
                        que.emplace(outdegree[neigh],neigh);
                }
            }
            count++;
        }
        return count;
    }
    int minNumberOfSemesters2(int n, vector<vector<int>>& relations, int k) {
        vector<int>preCource(n,0);
        //记录每个课程的先修课程，用二进制|可以得到
        //例如pre[1]=0110，说明1的先修课程是2和3
        for(auto &r:relations){
        int p=r[0]-1;
        int a=r[1]-1;
        preCource[a]|=1<<p;
        }
        int totalCount=1<<n;
        //0为不需要上任何课，学期数为0
        vector<int>dp(totalCount,16);
        dp[0]=0;
        vector<int>cnt(totalCount);
        //可以计算出每个i的二进制中1的个数
        cnt[0]=0;
        for(int i=1;i<totalCount;i++){
            cnt[i]=cnt[i>>1]+(i&1);
        }
        //taken表示已经上过的课程 take=0111,表示课程1 2 3 已经上过了
        for(int take=0;take<totalCount;take++){
            if(dp[take]>n)
                continue;
            int cur=0;
            // 在上过taken的基础上，还有哪些课可以上，要满足两个条件
            // 1. ((taken & (1 << j)) == 0) 表示这个课在taken中没上过
            // 2. ((prerequisite[j] & taken) == prerequisite[j]) 表示这个课的先修课已经上完了
            for(int j=0;j<n;j++)
            {

                if((take&(1<<j))==0&&((preCource[j]&take)==preCource[j]))
                {
                    // 存这学期可以上的课，注意，可以上不代表一定要上，也不一定要上满
                    // 这题的本质是NPC问题，任何贪心的思想都是错的，选择cur中的课来上的这个操作，用下面枚举子集的方法实现
                    cur|=(1<<j);
                }
            }
            //枚举cur的子集，比如cur=111 它的子mask集合就是{111, 110, 101 011, 100, 010, 001}
            for(int subMask=cur;subMask!=0;subMask=subMask-1&cur){
                //这学期学的课程数量不超过k
                if(cnt[subMask]<=k){
                    dp[take|subMask]=min(dp[take|subMask],dp[take]+1);
                }
            }
        }
        return dp[totalCount-1];
    }
};


#endif //LEETCODE_SOLUTION43_H
